/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-11-02
 * Time: 18:56
 */
/*
暴力解法会超时
class Solution3 {
    public int mySqrt(int x) {
        if(x == 0){
            return 0;
        }
        int a = 0 , sum = 0;
        for(int i = 1 ; ; i++ ){
            a = i;
            int result = a^2;
            if(result > x){
                a = a-1;
                break;
            }else if(result < x){
                continue;
            }else{
                break;
            }
        }
        return a;

    }
}
*/
class Solution3 {
    public int mySqrt(int x) {
        long left = 0 , right = x ;
        if(x < 1 ){
            return 0;
        }
        long mid = 0;//mid的平方越界了
        while(left < right){
            mid = left + (right - left + 1)/2;
            if(mid * mid <= x){
                left = mid;
            }else{
                right = mid - 1 ;
            }
        }
        return (int)left;//强转为int类型
    }
}



public class Test3 {
    public static void main(String[] args) {
        Solution3 s = new Solution3();
        s.mySqrt(4);
    }
    
}
